package Leetcode.搜索与回溯;

import java.util.*;

/**
 * @Author kirito
 * @Date 2023/11/15 10:07
 * @PackageName:Leetcode.搜索与回溯
 * @ClassName: 全排列
 * @Description:
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 示例 2：
 *
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * 示例 3：
 *
 * 输入：nums = [1]
 * 输出：[[1]]
 * @Version 1.0
 */
public class 全排列 {
    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        // 使用一个动态数组保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                     List<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        if (depth == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;

                dfs(nums, len, depth + 1, path, used, res);
                // 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
    /**
     * #include <stdio.h>
     * #include <stdlib.h>
     * #include <string.h>
     *
     * #define MAX 10000
     *
     * void dfs(int *nums, int numsSize, int depth, int *path, int pathSize,
     *     int *used, int **return_arr, int *returnSize, int **returnColumnSizes) {
     *     if (depth == numsSize) {
     *         // 复制路径到结果数组
     *         return_arr[*returnSize] = (int *)malloc(numsSize * sizeof(int));
     *         (*returnColumnSizes)[*returnSize] = pathSize;
     *         memcpy(return_arr[*returnSize], path, numsSize * sizeof(int));
     *         (*returnSize)++;
     *         return;
     *     }
     *
     *     for (int i = 0; i < numsSize; i++) {
     *         if (!used[i]) {
     *             path[pathSize] = nums[i];
     *             used[i] = 1;
     *             dfs(nums, numsSize, depth + 1, path, pathSize + 1, used, return_arr, returnSize, returnColumnSizes);
     *             // 回溯
     *             used[i] = 0;
     *         }
     *     }
     * }
     *
     * int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
     *     int **return_arr = (int **)malloc(MAX * sizeof(int *));
     *     *returnColumnSizes = (int *)malloc(MAX * sizeof(int));
     *     *returnSize = 0;
     *     int *path = (int *)malloc(numsSize * sizeof(int));
     *     int *used = (int *)calloc(numsSize, sizeof(int));
     *
     *     dfs(nums, numsSize, 0, path, 0, used, return_arr, returnSize, returnColumnSizes);
     *
     *     free(path);
     *     free(used);
     *     return return_arr;
     * }
     *
     * int main() {
     *     int nums[] = {1, 2, 3};
     *     int numsSize = sizeof(nums) / sizeof(nums[0]);
     *     int returnSize;
     *     int *returnColumnSizes;
     *
     *     int **return_arr = permute(nums, numsSize, &returnSize, &returnColumnSizes);
     *
     *     // 打印结果
     *     for (int i = 0; i < returnSize; i++) {
     *         for (int j = 0; j < returnColumnSizes[i]; j++) {
     *             printf("%d ", return_arr[i][j]);
     *         }
     *         printf("\n");
     *         free(return_arr[i]); // 释放每个排列的内存
     *     }
     *     free(return_arr); // 释放排列数组的内存
     *     free(returnColumnSizes); // 释放列大小的内存
     *
     *     return 0;
     * }
     */
}
